Search results for "Probability of error"
showing 3 items of 3 documents
Optimal one-shot quantum algorithm for EQUALITY and AND
2017
We study the computation complexity of Boolean functions in the quantum black box model. In this model our task is to compute a function $f:\{0,1\}\to\{0,1\}$ on an input $x\in\{0,1\}^n$ that can be accessed by querying the black box. Quantum algorithms are inherently probabilistic; we are interested in the lowest possible probability that the algorithm outputs incorrect answer (the error probability) for a fixed number of queries. We show that the lowest possible error probability for $AND_n$ and $EQUALITY_{n+1}$ is $1/2-n/(n^2+1)$.
Grover’s Algorithm with Errors
2013
Grover’s algorithm is a quantum search algorithm solving the unstructured search problem of size n in \(O(\sqrt{n})\) queries, while any classical algorithm needs O(n) queries [3].
Indistinguishability-enabled coherence for quantum metrology
2019
Quantum coherence plays a fundamental and operational role in different areas of physics. A resource theory has been developed to characterize the coherence of distinguishable particles systems. Here we show that indistinguishability of identical particles is a source of coherence, even when they are independently prepared. In particular, under spatially local operations, states that are incoherent for distinguishable particles, can be coherent for indistinguishable particles under the same procedure. We present a phase discrimination protocol, in which we demonstrate the operational advantage of using two indistinguishable particles rather than distinguishable ones. The coherence due to th…